package com.benben.springSecurity.weiwei;

public class wordSearch {
    boolean[][] visited;
    int x,y;
    int[][] d= {{-1,0},{0,1},{1,0},{0,-1}};
    public boolean exist(char[][] board,String word){
        if(board == null || board.length==0 || word == null) {
            return false;
        }
        x = board.length;
        y = board[0].length;
        visited = new boolean[x][y];
        for (int i=0;i<x;i++){
            for (int j=0;j<y;j++){
                //尝试从每一个点出发进行搜索，如果搜索到了就表明存在这个单词，直接返回true
                if(process(board,i,j,word,0)){
                    return true;
                }
            }
        }
        return false;
    }

    public boolean process(char[][] board,int row,int col,String word,int index){
        if(index == word.length()-1){
            return board[row][col] == word.charAt(index);
        }
        if(board[row][col] == word.charAt(index)){
            visited[row][col] = true;
            //分别从四个方向进行搜索
            for(int i=0;i<4;i++){
                int newRow = row + d[i][0];
                int newCol = col + d[i][1];
                if(legal(newRow,newCol) && !visited[newRow][newCol] && process(board,newRow,newCol,word,index+1)){
                    return true;
                }
            }
            visited[row][col] = false;
        }
        return false;
    }

    public boolean legal(int row,int col){
        return row >=0 && row < x && col >= 0 && col < y;
    }
}
